package pers.qianyu.month_202012.date_20201204;

import java.util.*;

/**
 * [Leetcode 每日一题]
 * 659. 分割数组为连续子序列
 * https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/
 *
 * @author mizzle rain
 * @date 2020-12-04 10:01
 */
public class IsPossible {
    /**
     * 哈希表 + 贪心
     */
    public boolean isPossible(int[] nums) {
        HashMap<Integer, Integer> countNum = new HashMap<>();
        for (int num : nums) {
            countNum.put(num, countNum.getOrDefault(num, 0) + 1);
        }
        HashMap<Integer, Integer> tail = new HashMap<>();
        for (int num : nums) {
            int preTailCount = tail.getOrDefault(num - 1, 0);

            int curCount = countNum.getOrDefault(num, 0);
            int nextCount = countNum.getOrDefault(num + 1, 0);
            int nextNextCount = countNum.getOrDefault(num + 2, 0);

            if (curCount <= 0) {
                continue;
            } else if (preTailCount > 0) {
                countNum.put(num, curCount - 1);
                tail.put(num - 1, preTailCount - 1);
                tail.put(num, tail.getOrDefault(num, 0) + 1);
            } else if (nextCount > 0 && nextNextCount > 0) {
                countNum.put(num, curCount - 1);
                countNum.put(num + 1, nextCount - 1);
                countNum.put(num + 2, nextNextCount - 1);
                tail.put(num + 2, tail.getOrDefault(num + 2, 0) + 1);
            } else {
                return false;
            }
        }
        return true;
    }
}
